package segment_tree

func NewSegmentTree(arr []int) SegmentTree {
	N := len(arr)
	copyA := CopyArrToSegmentDes(arr)
	segT := SegmentTree{}
	segT.sum  = make([]int, N<<2)
	segT.lazy = make([]int, N<<2)
	segT.update = make([]bool, N<<2)
	segT.change = make([]int, N<<2)
	segT.Build(copyA, 1, N, 1)
	return segT
}

type SegmentTree struct {
	sum []int
	lazy []int
	update []bool
	change []int
}

func (s *SegmentTree) Update (L, R, num, l, r, rt int) {
	if L <= l && r <= R {
		s.update[rt] = true
		s.change[rt] = num
		s.sum[rt] = (r-l+1)*num
		s.lazy[rt] = 0
		return
	}
	mid := (r+l)>>1
	s.PushDown(rt, mid-l+1, r-mid)
	if L <= mid {
		s.Update(L, R, num, l, mid, rt<<1)
	}
	if R >= mid {
		s.Update(L, R, num, mid+1, r, rt<<1|1)
	}
	s.PushUp(rt)
}

func (s *SegmentTree) Add (L, R, num, l, r, rt int) {
	if L <= l && r <= R {
		s.lazy[rt] += num
		s.sum[rt] += num*(r-l+1)
		return
	}
	mid := (l+r)>>1
	s.PushDown(rt, mid-l+1, r-mid)
	if L <= mid {
		s.Add(L, mid, num, l, r, rt<<1)
	}
	if R >= mid {
		s.Add(mid+1, R, num, l, r, rt<<1|1)
	}
	s.PushUp(rt)
}

func (s *SegmentTree) PushDown (rt, ln, rn int){
	if s.update[rt] == true {
		s.update[rt<<1] = true
		s.update[rt<<1|1] = true
		s.change[rt<<1]   = s.change[rt]
		s.change[rt<<1|1] = s.change[rt]
		s.sum[rt<<1] =   ln*s.change[rt]
		s.sum[rt<<1|1] = rn*s.change[rt]
		s.lazy[rt<<1] = 0
		s.lazy[rt<<1|1] = 0
		s.update[rt] = false
	}
	if s.lazy[rt] != 0 {
		s.lazy[rt<<1] += s.lazy[rt]
		s.lazy[rt<<1|1] += s.lazy[rt]
		s.sum[rt<<1] += ln*s.lazy[rt]
		s.sum[rt<<1|1] += rn*s.lazy[rt]
		s.lazy[rt] = 0
	}
}

func (s *SegmentTree) Query (L, R, l, r, rt int) int {
	if L <= l && r <= R {
		return s.sum[rt]
	}
	mid := (l+r)>>1
	var ans int
	s.PushDown(rt, mid-l+1, r-mid)
	if L <= mid {
		ans += s.Query(L, R, l, mid, rt<<1)
	}
	if R >= mid+1 {
		ans += s.Query(L, R,  mid+1, r, rt<<1|1)
	}
	return ans
}

func (s *SegmentTree) Build(arr []int, L, R, rt int) {
	if L == R {
		s.sum[rt] = arr[L]
		return
	}
	mid := (L+R) >> 1
	s.Build(arr, L, mid, rt<<1)
	s.Build(arr, mid+1, R, rt<<1|1)
	s.PushUp(rt)
}

func (s *SegmentTree) PushUp(rt int){
	s.sum[rt] = s.sum[rt<<1] + s.sum[rt<<1|1]
}

func CopyArrToSegmentDes(arr []int) []int {
	copyA := make([]int, len(arr)+1)
	for i:=1; i<len(copyA); i++ {
		copyA[i] = arr[i-1]
	}
	return copyA
}
